import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution460 {

    Map<Integer,Integer> map=new HashMap<>();
    Map<Integer,Integer> times=new HashMap<>();
    PriorityQueue<int[]> queue=new PriorityQueue<>((a,b)->a[1]==b[1]?a[2]-b[2]:a[1]-b[1]);
    int n;
    int count=0;

    public Solution460(int capacity) {
        n=capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)){
            return -1;
        }
        times.put(key,times.get(key)+1);
        queue.offer(new int[]{key,times.get(key),count});
        count++;
        return map.get(key);
    }

    public void put(int key, int value) {
        if (n==0){
            return;
        }
        if (map.containsKey(key)) {
            map.put(key, value);
            times.put(key,times.get(key)+1);
            queue.offer(new int[]{key,times.get(key),count});
        }else{
            if (map.size()==n){
                while (queue.peek()[1]!=times.get(queue.peek()[0])){
                    queue.poll();
                }
                int[] q=queue.poll();
                map.remove(q[0]);
                times.remove(q[0]);
            }
            map.put(key,value);
            times.put(key,1);
            queue.offer(new int[]{key,1,count});
        }
        count++;
    }

    public static void main(String[] args) {
        Solution460 solution460=new Solution460(2);
        solution460.put(1,1);
        solution460.put(2,2);
        System.out.println(solution460.get(1));
        solution460.put(3,3);
        System.out.println(solution460.get(2));
        System.out.println(solution460.get(3));
        solution460.put(4,4);
        System.out.println(solution460.get(1));
        System.out.println(solution460.get(3));
        System.out.println(solution460.get(4));
    }
}
